package practice_7_3;

public class Solution {
    /**
     * 山脉数组的峰顶索引
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray(int[] arr) {
        int len = arr.length;
        int left = 0, right = len - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            //   System.out.println("left: " + left + " mid: " + mid + " right: " + right);
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 寻找旋转排序数组中的最小值
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        int len = nums.length;
        int left = 0, right = len - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    /**
     * 点名
     * @param records
     * @return
     */
    public int takeAttendance(int[] records) {
        int len = records.length;
        int left = 0, right = len - 1;
        while(left < right) {
            int mid = (left + right + 1) / 2;
            if (records[mid] == mid) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (records[left] == left) {
            return left + 1;
        } else {
            return left;
        }
    }

    /**
     * 寻找数组的中心下标
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {
        int len = nums.length;
        int[] f = new int[len + 1];
        int[] g = new int[len + 1];
        for(int i = 0; i < len; i++) {
            f[i + 1] = f[i] + nums[i];
        }
        for(int i = len - 2; i >= 0; i--) {
            g[i] = g[i + 1] + nums[i + 1];
        }
        // System.out.println("f: " + Arrays.toString(f));
        // System.out.println("g: " + Arrays.toString(g));
        for(int i = 0; i < len; i++) {
            if (f[i] == g[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 矩阵区域和
     * @param mat
     * @param k
     * @return
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int maxX = (i + k >= m ? m - 1 : i + k) + 1;
                int maxY =  (j + k >= n ? n - 1 : j + k) + 1;
                int minX = (i - k <= 0 ? 0 : i - k);
                int minY = (j - k <= 0 ? 0 : j - k);
                //System.out.println("maxX: " + maxX + " maxY: " + maxY + "minX: " + minX + "minY: " + minY);
                res[i][j] = dp[maxX][maxY] - dp[maxX][minY] - dp[minX][maxY] + dp[minX][minY];
            }
        }
        return res;
    }
}
